package leetcode;

import javax.swing.tree.TreeNode;

/**
 * 最大二叉树
 */
public class Solution16 {
    public TreeNode constructMaximumBinaryTree(int[] nums) {
        return constructMaximumBinaryTree1(nums,0,nums.length);
    }

    public TreeNode constructMaximumBinaryTree1(int[] nums,int leftIndex,int rightIndex){
        if(rightIndex - leftIndex < 1){
            return null;
        }
        //判断只有一个元素
        if(rightIndex - leftIndex == 1){
            return new TreeNode(nums[leftIndex]);
        }
        //最大索引所在位置
        int maxIndex  = leftIndex;
        int maxValue = nums[maxIndex];
        for(int i = leftIndex + 1 ; i < rightIndex ; i++ ){
            if(nums[i] > maxValue){
                maxValue = nums[i];
                maxIndex = i;
            }
        }
        TreeNode node = new TreeNode(maxValue);
        node.left = constructMaximumBinaryTree1(nums,leftIndex,maxIndex);
        node.right = constructMaximumBinaryTree1(nums,maxIndex + 1,rightIndex);
        return node;
    }
}
